package insertionSort;

import selectionSort.ArrayGenerator;
import selectionSort.SortingHelper;

public class InsertionSort<E extends Comparable<E>> {
    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 1; i < arr.length; i++) {
            E tmp = arr[i];
            int j;
            for (j = i; j-1 >= 0 && tmp.compareTo(arr[j - 1]) < 0; j--)
                arr[j] = arr[j - 1];
            arr[j] = tmp;
        }
    }

    /**
     * 将arr[l,r]排序
     * @param arr
     * @param l
     * @param r
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        for (int i = l; i <=r; i++) {
            E tmp = arr[i];
            int j;
            for (j = i; j-1 >= l && tmp.compareTo(arr[j - 1]) < 0; j--)
                arr[j] = arr[j - 1];
            arr[j] = tmp;
        }
    }

    public static void main(String[] args) {
        int n = 10000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        SortingHelper.sortTest("InsertionSort",arr);
    }
}
